package lanQiaoBei.动态规划.线性dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//https://www.likecs.com/show-307180983.html
//思路：经过分析发现在朴素dp的第二层循环中在枚举前一个数的时候并不是每个数都需要枚举的，只需要枚举每一种长度中以较小数结尾的数就行了
public class 最长上升子序列加优化 {
       static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
       final static int N=100010;
       static int a[]=new int[N],lr[]=new int[N],n,idx;
       
       public static void main(String[] ss) throws IOException {
		      n=Integer.parseInt(br.readLine());
		      ss=br.readLine().split(" ");
		      for(int i=0;i<n;i++)
		    	  a[i]=Integer.parseInt(ss[i]);
		      int len=0;
		      lr[0]=-(int)(2e9);
		      for(int i=0;i<n;i++){
		    	  //二分找到区间内最后一个比ai小的数
		    	  int l=0,r=len;
		    	  while(l<r){
		    		  int mid=l+r+1>>1;
		    	      if(lr[mid]<a[i])l=mid;
		    	      else r=mid-1;
		    	  }
		    	  len=Math.max(len,r+1);
		    	  lr[r+1]=a[i];
		      }
		      System.out.print(len);
	}
}